package cn.hesion.leetcode;
/**
 * ClassName: AllPathsSourceTarget <br/>
 * Description: <br/>
 * date: 2022/5/30 6:14<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 797. 所有可能的路径
 * @author: hesion
 * @create: 2022-05-30 06:14
 **/
public class AllPathsSourceTarget {
    List<List<Integer>> paths = new ArrayList<List<Integer>>();
    List<Integer> stk =new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        stk.add(0);
        dfs(n,graph,0);
        return  paths;
    }

    void dfs(int n ,int[][] graph,int now){
        if(now==n-1){
            ArrayList<Integer> tmpStk = new ArrayList<>(stk);
            paths.add(tmpStk);
            return;
        }
        for (int i = 0; i < graph[now].length; i++) {
            stk.add(graph[now][i]);
            dfs(n,graph,graph[now][i]);
            stk.remove(stk.size()-1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = new AllPathsSourceTarget().allPathsSourceTarget(new int[][]{
                new int[]{1, 2},
                new int[]{3},
                new int[]{3},
                new int[]{}
        });
        lists.forEach(System.out::println);
    }

}
